package com.zecan.test;

import javax.swing.tree.TreeNode;
import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/20
 * \* Time: 10:01
 * \* Description:
 * \
 */
public class Solution {
    public static void main(String[] args) {
     /*   int[] arr = new int[]{2,3,3,4,5,5};
      TreeNode root =  new TreeNode(arr[0]);
      root.left = new TreeNode(arr[1]);
        root.right = new TreeNode(arr[2]);
        root.left.left = new TreeNode(arr[3]);
        root.left.right = new TreeNode(arr[4]);
        root.right.left = new TreeNode(arr[5]);

        System.out.println(isSymmetric(root));*/
    /*    int[] arr = new int[]{3, 5, 7, 4, 5, 3, 8, 0, 5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));*/
        int[] arr = new int[]{4, 3, 1, 2, 7, 10, 8};
        radix(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int leftMinIndex(int[] arr, int left, int right, int searchInt) {
        int t = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 获取中间值
            if (arr[mid] >= searchInt) {
                t = mid;
                right = mid - 1;
            }
            if (arr[mid] < searchInt) {
                left = mid + 1;
            }
        }
        return t;
    }

    //局部最小值
    public static int minIndex(int[] arr, int left, int right) {
        if (arr == null) return -1;

        if (arr.length == 1) return 0;
        if (arr.length > 1 && arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;
        left = 1;
        right = arr.length - 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }



    public static boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricTree(root.left, root.right);
    }

    public static boolean isSymmetricTree(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree == null) return true;

        if (leftTree == null || rightTree == null) return false;

        if (leftTree.val != rightTree.val) return false;

        return isSymmetricTree(leftTree.left, rightTree.right) && isSymmetricTree(leftTree.right, rightTree.left);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) {
            return false;
        }
        if (p.left == null && p.right == null
                && q.left == null && q.right == null && p.val == q.val) {
            return true;
        }
        if (p.val == q.val) {
            return isSameTree(p.left, q.right) && isSameTree(p.right, q.right);
        } else {
            return false;
        }

    }

    boolean isSame(TreeNode p, TreeNode q) {
        if (p.left != null && q.left != null) {
            return isSame(p.left, q.left);
        }
        if (p.right != null && q.right != null) {
            return isSame(p.right, q.right);
        }
        if (p.val != q.val) {
            return false;
        } else {
            return true;
        }

    }

    public void infixOrder(TreeNode root) {
        infixOrder(root.left);
        System.out.println(root.val);
        infixOrder(root.right);
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return binarySearchTree(nums, 0, nums.length - 1);
    }

    public TreeNode binarySearchTree(int[] nums, int left, int right) {
        if (left > right) return null; // 左闭右闭区间，当left < right 时终止递归
        TreeNode root = new TreeNode();
        int mid = (left + right) / 2;
        root.val = nums[mid];
        root.left = binarySearchTree(nums, left, mid - 1);
        root.right = binarySearchTree(nums, mid + 1, right);
        return root;
    }

    //小和问题
    public static void smallAnd(int[] arr, int left, int right) {
        if (arr == null) return;

        if (arr.length < 2) {
            return;
        }
        mergeSort(arr, left, right);
    }

    public static int mergeSort(int[] arr, int left, int right) {
        if (left == right) return 0;
        int mid = left + (right - left) / 2;

        return mergeSort(arr, left, mid) +// 左分区的排序完得到的小和
                mergeSort(arr, mid + 1, right) +//加上右分区排序完得到的小和
                merge(arr, left, mid, right);//再加上最终排序得到的小和的结果返回

    }


    public static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int index = 0; // 指向临时数组的指针
        int p1 = left; // 左区间的指针
        int p2 = mid + 1; //右区间的指针

        int res = 0;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] > arr[p2]) {
                for (int tmp = p1; tmp <= mid; tmp++) {
                    System.out.println("左数: " + arr[tmp] + "右数" + arr[p2]);
                }
                temp[index++] = arr[p2++];
                res += mid - p1 + 1;
            } else {

                temp[index++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
            temp[index++] = arr[p1++];
        }
        while (p2 <= right) {
            temp[index++] = arr[p2++];
        }
        index = 0;
        while (left <= right) {
            arr[left++] = temp[index++];
        }
        return res;
    }

    // 实现给定一个数组，和一个数将数组中的大于这个数的放在右边小于这个数的放在左边
    public static void sortArr(int[] arr, int target) {
        int i, j;
        for (i = 0, j = 0; i < arr.length; ) {
            if (arr[i] <= target) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j++;
            } else {
                i++;
            }
        }
    }

    //荷兰国旗问题 给定一个数组，和一个数要求在数组中左边是小于这个数中间是等于这个数，右边是大于这个数
    public static void sortArray(int[] arr, int target) {
        int i = 0, j = arr.length - 1; // 定义左右区间的指针
        int k = 0; // 定义指向数组判定大小的指针
        int temp = 0; // 用于交换的中间变量
        while (k <= j) { //当数组指针与右区间指针不相遇是循环继续
            if (arr[k] < target) {
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                k++;
                i++;
            } else if (arr[k] > target) {
                temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
                j--;
            } else {
                k++;
            }
        }
    }

    //堆排序
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) { // 如果当前数组为空 或者 当前数组长度为 1时直接返回
            return;
        }
        //构造大顶堆
        int heapSize = arr.length - 1;
        for (int i = arr.length / 2 - 1; i >= 0; i--) { // 构造大根堆的第二种方法，从最后一个非叶子结点开始构造大根堆
            heapify(arr, i, arr.length);
        }

        swap(arr, 0, heapSize);
        --heapSize;
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, heapSize);
            --heapSize;
        }
    }

    //构造大顶堆的方法
    // index 是传递过来的从哪开始进行大顶堆构造
    // 此方法的作用是 不断添加元素的过程中向上比较父节点是否比它小如果是与父节点交换
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    //此方法的作用是将第一个数和最后一个数进行交换时再将原来的树调整成堆
    public static void heapify(int[] arr, int i, int heapSize) {
        int index = i * 2 + 1;// 获取当前左孩子的下标
        while (index < heapSize) {
            //寻找左右孩子哪个更大
            int largest = (index + 1 < heapSize) && (arr[index + 1] > arr[index]) ? index + 1 : index;
            int k = i; // 保存父节点下标
            k = arr[index] < arr[i] ? i : largest;
            if (k == i) break;
            swap(arr, i, largest);
            i = largest;
            index = i * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void sort(int[] arr, int k) {
        // 首先先构造一个小根堆数组
        int[] heap = Arrays.copyOf(arr, k);
        //构造小根堆
        for (int i = k / 2 - 1; i >= 0; i--) { // 因为一开始的小根堆长度为k 从最后一个非叶子结点开始构造小根堆
            sortHeap(heap, i, k);
        }
        //当小根堆构造完毕之后，根据题意 每个元素排序最多移动不超过k 所以通过循环将小根堆的根节点放入到原数组第一个位置上依次
        int i = k;
        for (int index = 0; i < arr.length; i++) {
            arr[index++] = heap[0]; //将小根堆的根节点放入到原数组的第一个位置上
            heap[0] = arr[i]; //将k之后的第一个元素放入到小根堆第一个位置上
            sortHeap(heap, (k / 2 - 1), k); //再重新构造成一个小根堆
        }

        for (; k > 0; k--) {//堆的长度不足k
            arr[arr.length - k] = heap[0];
            heap[0] = heap[k - 1];
            sortHeap(heap, (k / 2 - 1), k);
        }
    }

    public static void sortHeap(int[] arr, int i, int length) {
        if (i < 0) return;
        int index = i * 2 + 1; // 从当前结点的左孩子开始
        while (index < length) {
            // 如果当前结点有右孩子 且 右孩子的值比左孩子小
            int largest = (index + 1) < length && (arr[index] > arr[index + 1]) ? index + 1 : index;

            int k = arr[largest] > arr[i] ? largest : i;
            if (k == largest) break;  // 如果子孩子大于父节点那么就直接退出循环
            swap(arr, largest, k); //否则就进行交换
            i = largest;
            index = i * 2 + 1; // 继续查找其左孩子
        }
    }

    public static void radix(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int digit = getMax(arr); // 获取数组中的最大值，以便知晓进出桶几次
        radixSort(arr, 0, arr.length - 1, digit);
    }

    //桶排序主要算法
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10; // 默认桶的大小为10
        int[] bucket = new int[R - L + 1]; // 构造桶的大小
        //1.先将每个数的个位数获取
        for (int d = 1; d <= digit; d++) { // d 代表 进出桶的次数

            int[] count = new int[radix]; // 计数器代表下标位置的桶有多少个数据
            for (int i = 0; i <= R; i++) { // 此方法的作用是获取当前原数组中的个位数(十位百位等)放入对应的桶中
                int j = getDigit(arr[i], d);
                count[j]++; //计数器自增1
            }
            //再将该计数器数组转换成前缀数组 从1开始当前下标的值等于自身加上前一个位置的值
            for (int j = 1; j < radix; j++) {
                count[j] = count[j - 1] + count[j];
            }
            //再将原数组中从右往左依次按照 d 的大小在计数器中找到对应的下标放入桶中
            for (int i = R; i >= L; i--) {
                int j = getDigit(arr[i], d); //获取最右边的数据在计数器中的值
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            //再将桶中的元素依次取出放入到数组中
            for (int i = 0, index = 0; i <= R; i++, index++) {
                arr[i] = bucket[index];
            }
        }
    }

    //获取最大值
    public static int getMax(int[] arr) {
        int maxVal = Integer.MIN_VALUE;
        for (int i : arr) {
            if (i > maxVal) {
                maxVal = i;
            }
        }
        int res = 0;
        while (maxVal != 0) {
            maxVal /= 10;
            res++;
        }
        return res;
    }

    // 获取当前传递过来的数据的个位十位百位等
    public static int getDigit(int i, int d) {
        return ((i / ((int) Math.pow(10, d))) % 10);
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
